using System;
using System.Collections;
using Slaks.GraphExtensions;
using Slaks.SuperGraphExtensions.Containers;

namespace Slaks.Graphs.ShenkerGraph.Algorithms
{
	public class SlaksGraphClustering
	{
		private SuperGraphDistanceMeasure m_graphDistanceMeasure;
		private int m_numberOfClusters;

		private SuperGraphList[] m_graphClusters;

		public SlaksGraphClustering(SuperGraphList graphList, int numberOfClusters, SuperGraphDistanceMeasure graphDistanceMeasure)
		{
			if (graphList == null || graphList.Count == 0) throw new GraphException("There are no supergraphs in the list");
			if (numberOfClusters <= 0) throw new GraphException("Number of clusters must be greater then 0");
			if (graphList.Count < numberOfClusters) numberOfClusters = graphList.Count;

			m_graphDistanceMeasure = graphDistanceMeasure;
			m_numberOfClusters = numberOfClusters;

			this.Init(graphList, numberOfClusters);
		}

		public SuperGraphList[] GetSuperGraphClusters()
		{
			return m_graphClusters;
		}

		private void Init(SuperGraphList superGraphList, int numberOfClusters)
		{
			m_graphClusters = new SuperGraphList[numberOfClusters];
			for (int i = 0; i < numberOfClusters; i++)
			{
				m_graphClusters[i] = new SuperGraphList();
			}

			int clusterNumber;
			Random rand = new Random(unchecked((int) DateTime.Now.Ticks));
			foreach (SuperGraph superGraph in superGraphList)
			{
				clusterNumber = rand.Next(numberOfClusters);
				m_graphClusters[clusterNumber].Add(superGraph);
			}

			for (int i = 0; i < numberOfClusters; i++)
			{
				SuperGraph superGraph;
				if (m_graphClusters[i].Count > 0)
				{
					superGraph = m_graphClusters[i][0];
					m_graphClusters[i].SetCentroid(superGraph);
				}
			}
		}

		/// <summary>
		/// Get the number of clusters
		/// </summary>
		/// <returns></returns>
		public int GetNumberOfClusters()
		{
			return m_numberOfClusters;
		}

		/// <summary>
		/// Apply the Shenker Algorithm
		/// </summary>
		public void Apply()
		{
			bool isChanged = true;

			while (isChanged == true)
			{
				isChanged = this.DetermineCentroids();
				//Console.WriteLine("determine :"  + this.CountGraphs());
				if (isChanged == true)
				{
					this.AssignGraphs();
					//Console.WriteLine("apply :"  + this.CountGraphs());
				}
			}
		}

		/// <summary>
		/// Determine centroids for clusters and return whether the centroids were changed
		/// </summary>
		/// <returns>true if centroids were altered otherwise return false</returns>
		private bool DetermineCentroids()
		{
			bool isChanged = false;
			bool result;
			foreach (SuperGraphList superGraphCluster in m_graphClusters)
			{
				result = superGraphCluster.DetermineCentroid(m_graphDistanceMeasure);
				if (result == true) isChanged = true;
			}
			return isChanged;
		}

		private void AssignGraphs()
		{
			double minDistance;
			double tempDistance;
			int cluster = 0;
			SuperGraph centroid;
			SuperGraph currentSuperGraph;

			//holds graphs that must be removed
			ArrayList graphsToRemove = new ArrayList();
			for (int i = 0; i < m_graphClusters.Length; i++)
			{
				graphsToRemove.Clear();
				for (int j = 0; j < m_graphClusters[i].Count; j++)
				{
					minDistance = double.MaxValue;
					cluster = i; //current cluster to which currentGraph belongs
					currentSuperGraph = m_graphClusters[i][j];

					if (currentSuperGraph == m_graphClusters[i].GetCentroid()) continue;

					for (int k = 0; k < m_graphClusters.Length; k++)
					{
						centroid = m_graphClusters[k].GetCentroid();
						if (centroid == null) continue;
						tempDistance = m_graphDistanceMeasure(centroid, currentSuperGraph);
						if (minDistance > tempDistance)
						{
							minDistance = tempDistance;
							cluster = k;
						}
					}

					//the graph belongs to another cluster
					if (cluster != i)
					{
						m_graphClusters[cluster].AddSuperGraphToTemporalList(currentSuperGraph);
						graphsToRemove.Add(currentSuperGraph);
					}
				} //end of for

				foreach (SuperGraph superGraph in graphsToRemove)
				{
					m_graphClusters[i].Remove(superGraph);
				}

			} //end of for

			for (int i = 0; i < m_graphClusters.Length; i++)
			{
				m_graphClusters[i].MergeTemporalList();
			}

		}

		public int CountGraphs()
		{
			int count = 0;
			foreach (SuperGraphList cluster in this.GetSuperGraphClusters())
			{
				count += cluster.Count;
			}
			return count;
		}
	}
}